package sort.test3_31;

import java.awt.*;
import java.util.ArrayList;
import java.util.Collections;

public class BucketSort {

//  CKG TODO 2023/3/31:   找到数组的最大数值和最小数值　　　桶的数目＝(max-min)/数组长度＋１　　　
//  CKG TODO 2023/3/31:     每个元素放入桶中的序号　　(nums[i]-min)/numsLength   然后将桶中元素排序　最后汇总所有桶中的元素

    public  void sort(int[] nums){
        if (nums.length==0){
            return;
        }
        int min=Integer.MAX_VALUE;
        int max=Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            min=Math.min(min,nums[i]);
            max=Math.max(max,nums[i]);
        }
        int bucketCount=(max-min)/ nums.length+1;

//        ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>(bucketCount)>(1);

        //  CKG TODO 2023/3/31: 下面这两个地方　关键
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            lists.add(new ArrayList<>());
        }


        for (int i = 0; i <nums.length; i++) {
            lists.get((nums[i]-min)/ nums.length).add(nums[i] );
        }

        for (int i = 0; i < bucketCount; i++) {
            Collections.sort(lists.get(i));
        }

        for (int i = 0; i < bucketCount; i++) {
            ArrayList<Integer> list = lists.get(i);
            int size = list.size();
            for (int j = 0; j <size ; j++) {
                System.out.println(list.get(j));
            }
        }

    }

    public static void main(String[] args) {
        BucketSort bucketSort = new BucketSort();
        int arr[] = {10,5,11,6};
        bucketSort.sort(arr);
    }
}
